<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>最小点覆盖问题的几种近似算法</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <h1>最小点覆盖问题的几种近似算法</h1>

<h2>最小点覆盖问题</h2>

<p>最小点覆盖是这样一个问题, 给一张图\(G = &lt;V, E&gt;\) , 求一个势最小的集合\(A \subset V,s.t. \forall ab\in E,a\in A \bigvee b\in A\).</p>

<p>一般用\(VC\)来表示这个问题.</p>

<h2>VC的一种组合技术的近似算法</h2>

<p>一般所谓组合技术, 也并没有多大的难处.</p>

<p>贪就完事了.</p>

<p>按照某个顺序枚举每条边, 如果这条边的两个关联点没有被加入到\(A\)集合中去的话, 就全加入到\(A\)中.</p>

<p>不妨设最后\(|A|=2t\).</p>

<p>现在来估计一下最优解的大小.</p>

<p>先给出答案好了一定大于\(t\), 若是小于\(t\)的话, 按照上述的顺序枚举, 一定会发现一条不被覆盖的边.于是近似上界为\(\frac{2t}{t} = t\)</p>

<p>这是个相当容易分析的算法.</p>

<h2>VC的一种基于线性规划的近似算法</h2>

<p>我们可以先花10s来想一想怎么把\(VC\)表达成整数规划问题.</p>

<p>设\(x_{i}\)为\(i\)点是不是被加入到\(A\)中, 于是\(x_{i}\in \{0,1\}\), 显然优化函数为\(\min{\sum_{i=1}^{v}x_{i}}\), 约束条件为\(x_{i}+x_{j} \geq 1, ij \in E\) 以及 \(x_{i}\in \{0,1\}\).</p>

<p>但是这样还是\(NP\)问题, 我们对其中的整数型变量进行松弛, 即\(x_{i} \geq 0\).</p>

<p>现在就变成了一种线性规划问题. 可以通过椭球算法求解, 总之是一个\(P\)问题了.</p>

<p>之后要想办法把线性规划得到的解, 进行取整还原回原问题.</p>

<p>这一步骤就叫<q>取整</q>, 这一步的性能对整个算法的性能有着很大的影响.</p>

<p>在这个问题中如果\(x_{i} \geq \frac{1}{2}\), 我们就把它加入到\(A\)中, 这样可以保证每条边都被覆盖了, 证明可以通过反证法简单的得到, 这里就不再写了.</p>

<p>根据整数规划变换到线性规划的部分, 线性规划的解一定不会劣于整数规划得到的解.</p>

<p>由\(2x_{i} \geq 1\), 得到近似上界为2 (我实在不想写了咕咕咕</p>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>